package datastructure.sort;

import java.util.Comparator;

/**
 * Description：快速排序
 * Author: zhangc
 * Date：2017/6/19 21:13
 */
public final class QuickSort {

    public static <T extends Comparable<? super T>> void quickSort(T[] array, int start, int end) {
        /* 递归结束条件，一定不能少，否则栈溢出 */
        if (start > end)
            return;
        int i = start, j = end;
        T key = array[ i ];

        while (i < j) {
            while (j > i && array[ j ].compareTo(key) >= 0) {
                --j;
            }
            if (i < j) {
                array[ i++ ] = array[ j ];
            }
            while (i < j && array[ i ].compareTo(key) <= 0) {
                ++i;
            }
            if (i < j) {
                array[ j-- ] = array[ i ];
            }
        }
        array[ i ] = key;

        //左右的范围一定要这么写，不能有重合，否则会栈溢出
        quickSort(array, start, i - 1);
        quickSort(array, i + 1, end);
    }

    public static <T> void quickSort(T[] array, int start, int end, Comparator<? super T> comparator) {
        /* 递归结束条件，一定不能少，否则栈溢出 */
        if (start > end)
            return;
        int i = start, j = end;
        T key = array[ start ];
        while (i < j) {
            while (j > i && comparator.compare(array[ j ], key) < 0) {
                --j;
            }
            if (j > i) {
                array[ i++ ] = array[ j ];
            }
            while (i < j && comparator.compare(array[ i ], key) > 0) {
                ++i;
            }
            if (i < j) {
                array[ j-- ] = array[ i ];
            }
        }
        array[ i ] = key;
        //左右的范围一定要这么写，不能有重合，否则会栈溢出
        quickSort(array, 0, i - 1, comparator);
        quickSort(array, i + 1, end, comparator);
    }
}
